<?php
/**
 * @title 2646. 最小化旅行的价格总和
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {
    /**
     * @param Integer $n
     * @param Integer[][] $edges
     * @param Integer[] $price
     * @param Integer[][] $trips
     * @return Integer
     */
    function minimumTotalPrice($n, $edges, $price, $trips) {
        /**
         * @since 2023-12-06
         *      0
         *     /
         *    1
         *   / \
         *  2   3
         *
         * Trip | 路径上节点
         * ---------------------
         * 0->3     0,1,3
         * 2->1     2,1
         * 2->3     2,1,3
         *
         * Node | Price | Cnt | Total Cost
         * ----------------------------------
         *  0       2      1        2
         *  1       2      3        6
         *  2      10      2       20
         *  3       6      2       12
         *
         * Price*Cnt，树变成
         *      2
         *     /
         *    6
         *   / \
         * 20   12
         *
         * 2+6+20+12 = 40
         * 40-1-10-6=23
         */

        /**
         * @since 2023-12-06 点到点存在路径的集合
         */
        $pointToPointArray = [];
        foreach ($edges as list($s, $e)){
            $pointToPointArray[$s][$e] = $e;
            $pointToPointArray[$e][$s] = $s;
        }

        /**
         * @since 2023-12-06 旅行可能重复，格式化处理
         */
        $tripArray = [];
        foreach ($trips as list($s, $e)){
            /**
             * @since 2023-12-06 保证$s<=$e
             */
            if($s>$e){
                list($s, $e) = [$e, $s];
            } else {}

            /**
             * @since 2023-12-06 键值
             */
            $key = "{$s}-{$e}";
            if(isset($tripArray[$key])){
                $tripArray[$key][2] += 1;
            } else {
                $tripArray[$key] = [$s, $e, 1];
            }
        }
        // return $tripArray;

        /**
         * @since 2023-12-06 统计所有旅行，每个点的价值 = Price * Count
         */
        $pointCostArray = array_fill(0, $n, 0);

        /**
         * @since 2023-12-06 每次旅行的路径
         */
        $pathArray = [];
        foreach ($tripArray as list($s, $e, $cnt)){
            // echo str_repeat(PHP_EOL, 1), "trip=[{$s}, {$e}]";

            /**
             * @since 2023-12-06 起点终点一致
             */
            if($s == $e){
                $pathArray = [$s];
            } else {
                /**
                 * @since 2023-12-06 跳出循环
                 */
                $break = false;

                /**
                 * @since 2023-12-06 层次遍历，找到$s到$e的路径
                 */
                $nodeArray = [$s => [$s]];
                $copyPointToPointArray = $pointToPointArray;
                while($nodeArray){
                    /**
                     * @since 2023-12-06 下次层次遍历的点
                     */
                    $nextNodeArray = [];

                    /**
                     * @since 2023-12-06 遍历当层的点
                     */
                    foreach ($nodeArray as $point=>$bfsPathArray){
                        foreach ($copyPointToPointArray[$point] as $nextPoint){
                            /**
                             * @since 2023-12-06 阻止回头路
                             */
                            unset($copyPointToPointArray[$nextPoint][$point]);

                            /**
                             * @since 2023-12-06 更新路径
                             */
                            $newBfsPathArray = array_merge($bfsPathArray, [$nextPoint]);

                            /**
                             * @since 2023-12-06 到达终点$e
                             */
                            if($nextPoint == $e){
                                $pathArray = $newBfsPathArray;

                                $break = true;
                                break;
                            } else {}

                            /**
                             * @since 2023-12-06 下次遍历点
                             */
                            $nextNodeArray[$nextPoint] = $newBfsPathArray;
                        }

                        /**
                         * @since 2023-12-06 跳出循环
                         */
                        if($break){
                            break;
                        } else {}
                    }

                    /**
                     * @since 2023-12-06 跳出循环
                     */
                    if($break){
                        break;
                    } else {}

                    /**
                     * @since 2023-12-06 赋值下次层次遍历的点
                     */
                    $nodeArray = $nextNodeArray;
                }
            }

            /**
             * @since 2023-12-06 统计次数
             */
            // echo ", path=[", implode(",", $pathArray) ,"]";
            foreach ($pathArray as $point){
                $pointCostArray[$point] += $price[$point] * $cnt;
            }
        }
        // return $pointCostArray;

        /**
         * @since 2023-12-06 0为根节点，建立层次关系
         */
        $relationshipArray = [];
        $nodeArray = [0];
        while($nodeArray){
            /**
             * @since 2023-12-06 下次层次遍历的点
             */
            $nextNodeArray = [];

            /**
             * @since 2023-12-06 遍历当前层点
             */
            foreach ($nodeArray as $point){
                if(isset($pointToPointArray[$point])){
                    foreach ($pointToPointArray[$point] as $nextPoint){
                        /**
                         * @since 2023-12-06 下次遍历的点
                         */
                        $nextNodeArray[] = $nextPoint;

                        /**
                         * @since 2023-12-06 建立单向关系
                         */
                        $relationshipArray[$point][] = $nextPoint;
                        unset($pointToPointArray[$nextPoint][$point]);
                    }
                } else {}
            }

            /**
             * @since 2023-12-06 赋值下次层次遍历的点
             */
            $nodeArray = $nextNodeArray;
        }
        // return $relationshipArray;

        /**
         * @since 2023-12-06 避免重复计算
         */
        $this->dpArray = [];

        /**
         * @since 2023-12-06 获取最小价格总和
         */
        return self::MinCost($pointCostArray, $relationshipArray, 0);
    }

    /**
     * @title 返回最小价格总和
     * @author start2004
     * @since 2023-12-06 Created
     *
     * @param array $pointCostArray
     * @param array $relationshipArray
     * @param int $point
     * @return int
     */
    function MinCost(Array $pointCostArray = [], Array $relationshipArray = [], int $point = 0){
        if(isset($this->dpArray[$point])){
            return $this->dpArray[$point];
        } else {}

        /**
         * @since 2023-12-06 最小价格总和
         */
        $minCost = PHP_INT_MAX;

        /**
         * @since 2023-12-06 $point全价
         */
        $cost1 = $pointCostArray[$point];

        /**
         * @since 2023-12-06 $nextPoint到叶子节点，路径终点
         */
        if(!isset($relationshipArray[$point])){
            /**
             * @since 2023-12-06 直接半价
             */
            $this->dpArray[$point] = $cost1>>1;
            return ($cost1>>1);
        } else {
            /**
             * @since 2023-12-06 下一个层遍历
             */
            foreach ($relationshipArray[$point] as $nextPoint){
                /**
                 * @since 2023-12-06 下一层节点可以半价，可以全价
                 */
                $cost1 += self::MinCost($pointCostArray, $relationshipArray, $nextPoint);
            }
            $minCost = min($minCost, $cost1);
        }

        /**
         * @since 2023-12-06 $point半价
         */
        $cost2 = ($pointCostArray[$point]>>1);

        /**
         * @since 2023-12-06 下一层结点只能全价
         */
        foreach ($relationshipArray[$point] as $nextPoint){
            /**
             * @since 2023-12-06 全价节点
             */
            $cost2 += $pointCostArray[$nextPoint];

            /**
             * @since 2023-12-06 $nextPoint还有子节点
             */
            if(isset($relationshipArray[$nextPoint])){
                foreach ($relationshipArray[$nextPoint] as $next2Point){
                    $cost2 += self::MinCost($pointCostArray, $relationshipArray, $next2Point);
                }
            } else {}
        }
        $minCost = min($minCost, $cost2);
        // echo "point={$point}, 全价={$cost1}, 半价={$cost2}", PHP_EOL;

        /**
         * @return
         */
        $this->dpArray[$point] = $minCost;
        return $minCost;
    }
}

/**
 * @url http://127.0.0.1/leetcode/202312/2023.12.06_3.php
 */
$datas = [
    [4, [[0,1],[1,2],[1,3]], [2,2,10,6], [[0,3],[2,1],[2,3]]], // 23
    [4, [[0,1],[1,2],[1,3]], [2,2,10,6], [[0,3],[2,1],[2,3],[0,1]]], //
    [2, [[0,1]], [2,2], [[0,0]]], // 1
    [5, [[1,2],[2,0],[0,3],[3,4]], [12,26,22,12,2], [[3,3],[3,2],[3,0],[3,4],[1,1],[2,2],[4,0],[0,2],[2,3],[2,1],[4,2],[0,1],[4,2],[0,4],[0,3],[4,0],[4,0],[3,3],[4,3],[2,2],[4,2],[1,4],[3,2],[4,4],[4,2],[2,3],[4,3],[4,4],[4,2],[0,4],[4,2],[3,4],[4,0],[3,2],[3,1],[2,0],[0,4],[3,4],[2,0],[1,4],[4,2],[4,4],[2,1],[0,1],[4,1],[3,4],[0,4],[2,0],[2,0],[3,3],[4,4],[0,1],[0,1],[0,1],[2,0],[0,1],[3,1],[3,4],[3,4],[4,2],[0,4],[4,4],[3,2],[2,1],[3,2],[1,4],[1,0],[4,2],[4,3],[3,1],[4,4],[3,1],[1,0],[0,0],[0,0],[3,0],[0,2],[2,2],[3,3],[0,3]]], // 2037
    [10, [[0,4],[2,4],[6,3],[8,3],[3,4],[4,7],[7,5],[5,1],[1,9]], [10,6,4,8,8,6,10,8,2,2], [[9,6],[5,5],[8,4],[7,8],[4,5],[0,8],[3,4],[6,1],[8,0],[4,5],[7,5],[9,0],[6,3],[0,1],[3,9],[6,7],[1,5],[0,9],[0,4],[2,0],[0,3],[1,8],[5,3],[6,0],[6,4],[9,0],[8,7],[5,6],[3,6],[8,8],[7,8],[6,3],[5,7],[5,3],[8,7],[7,7],[2,5],[4,2],[0,8],[3,2],[7,2],[1,6],[2,7],[1,7]]], //
    [19, [[5,15],[6,3],[3,18],[7,12],[8,16],[9,17],[10,12],[13,12],[12,1],[15,11],[16,14],[14,0],[0,4],[4,2],[17,2],[2,1],[1,11],[11,18]], [104,62,114,158,22,2,108,164,44,100,96,98,142,140,48,40,134,146,56], [[6,11],[15,18],[9,10],[16,14],[11,2],[5,7],[17,0],[17,12],[14,14],[4,16],[16,8],[14,17],[16,8],[11,16],[16,10],[6,4],[2,5],[4,18],[11,3],[13,11],[11,2],[10,12],[17,13],[6,8],[13,3],[6,17],[9,7],[13,17],[11,12],[7,11],[6,6],[11,0],[2,9],[1,2],[16,4],[18,5],[14,11],[2,2],[5,2],[18,2],[15,16],[6,11],[18,0],[6,14],[0,13],[0,15],[2,13],[13,11],[7,15],[7,9],[16,16],[16,13],[18,18],[4,15],[16,14],[13,16],[8,13],[2,14],[8,4],[9,15],[17,10],[4,18],[6,18],[3,13],[6,2],[13,13],[15,3],[16,3],[15,17],[8,8],[16,18],[18,1],[3,4],[4,18],[7,1],[18,10],[12,7],[11,6],[10,11],[13,18],[7,5],[3,15],[7,5],[6,8],[0,16],[0,16],[15,10],[12,3],[5,14],[2,11],[5,9],[7,8],[8,10],[14,9],[15,10],[1,7],[12,3]]],
    [40, [[0,28],[6,29],[7,34],[8,5],[5,20],[9,12],[12,3],[13,11],[14,32],[18,3],[3,20],[22,15],[15,28],[26,25],[25,20],[20,17],[27,16],[28,2],[31,2],[2,21],[21,23],[23,4],[4,35],[32,19],[33,39],[34,10],[10,11],[11,16],[16,17],[17,1],[1,24],[24,30],[30,19],[19,39],[35,29],[29,38],[36,38],[37,39],[38,39]], [4,14,4,8,26,26,12,6,10,30,30,28,2,20,8,26,10,30,18,30,18,30,16,14,18,6,20,24,20,18,8,4,12,30,12,6,30,22,28,8], [[10,15],[5,21],[16,28],[0,31],[13,37],[22,27],[13,7],[23,10],[7,4],[0,11],[35,20],[7,12],[16,15],[21,6],[7,4],[5,25],[10,22],[10,1],[20,8],[20,23],[38,39],[20,2]]],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    if(count($data) <= 20){
        // var_dump($data);
    } else {
        var_dump(count($data));
    }

    $obj = new Solution();
    $result = $obj->minimumTotalPrice(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
